#include<iostream>
#include<utility>
#include<assert.h>
#include<vector>
using namespace std;


template<class K, class V>
class AVLTreeNode {
public:
    //构造函数
    AVLTreeNode(const pair<K,V>& kv)
    :_kv(kv)
    ,_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_bf(0)
    {}

    //成员变量
    pair<K,V> _kv;
    AVLTreeNode* _left;
    AVLTreeNode* _right;
    AVLTreeNode* _parent;
    int _bf;
};

template<class K, class V>
class AVLTree {
    typedef AVLTreeNode<K,V> Node;
public:
    AVLTree()
    :_root(nullptr)
    {}

    bool insert(const pair<K,V>& kv) {
        if(_root==nullptr){
            _root=new Node(kv);
            return true;
        }

        Node* parent=nullptr;
        Node* cur=_root;

        while(cur){
            if(cur->_kv.first<kv.first) {
                parent=cur;
                cur=cur->_right;
            }
            else if(cur->_kv.first>kv.first) {
                parent=cur;
                cur=cur->_left;
            }
            else{
                return false;
            }
        }

        cur=new Node(kv);
        if(kv.first<parent->_kv.first){
            parent->_left=cur;
        }
        else{
            parent->_right=cur;
        }
        cur->_parent=parent;

        while(parent){
            if(cur==parent->_left){                          //新增节点在父节点的左子节点时，父节点的平衡因子减减
                parent->_bf--;
            }
            if(cur==parent->_right){                         //新增节点在父节点的右子节点时，父节点的平衡因子加加
                parent->_bf++;
            }
            if(parent->_bf==0){                              //当父节点的平衡因子为0时，说明父节点的左右子树平衡
                break;
            }
            else if(parent->_bf==1||parent->_bf==-1){        //当父节点的平衡因子为1后者-1时，继续往上
                cur=parent;
                parent=parent->_parent;
            }
            else if(parent->_bf==2||parent->_bf==-2){        //当父节点的平衡因子为2后者-2时，说明当前父节点的左右子树不平衡，需要旋转调整
                if(parent->_bf==2&&cur->_bf==1){
                    RotateL(parent);
                }
                else if(parent->_bf==-2&&cur->_bf==-1){
                    RotateR(parent);
                }
                else if(parent->_bf==2&&cur->_bf==-1){
                    RotateRL(parent);
                }
                else if(parent->_bf==-2&&cur->_bf==1){
                    RotateLR(parent);
                }
                
                break;
            }
            else{
                assert(false);
            }
        }

        return true;
    }

    int Height(){
        return _Height(_root);
    }

    bool IsBlance(){
        return _IsBlance(_root);
    }

private:
    int _Height(Node* root){
        if(root==nullptr){
            return 0;
        }
        int leftheight=_Height(root->_left);
        int rightheight=_Height(root->_right);

        return leftheight > rightheight ? leftheight+1 : rightheight+1;
    }

    bool _IsBlance(Node* root){
        if(root==nullptr){
            return true;
        }

        int leftheight=_Height(root->_left);
        int rightheight=_Height(root->_right);

        if(rightheight-leftheight!=root->_bf){
            cout<<"blance factor flase:"<<root->_kv.first<<"->"<<root->_bf<<endl;
        }

        return abs(rightheight-leftheight)<2
               &&_IsBlance(root->_left)
               &&_IsBlance(root->_right);

    }

    //左单旋
    void RotateL(Node* parent){
        Node* cur=parent->_right;
        Node* curleft=cur->_left;
        Node* ppnode=parent->_parent;

        parent->_right=curleft;
        if(curleft){
            curleft->_parent=parent;
        }

        cur->_left=parent;
        parent->_parent=cur;

        if(ppnode){
            if(ppnode->_left==parent){
                ppnode->_left=cur;
                cur->_parent=ppnode;
            }
            else{
                ppnode->_right=cur;
                cur->_parent=ppnode;
            }
        }
        else{
            cur->_parent=nullptr;
            _root=cur;
        }

        cur->_bf=parent->_bf=0;
    }

    //右单旋
    void RotateR(Node* parent){
        Node* cur=parent->_left;
        Node* curright=cur->_right;
        Node* ppnode=parent->_parent;

        parent->_left=curright;
        if(curright){
            curright->_parent=parent;
        }

        cur->_right=parent;
        parent->_parent=cur;

        if(ppnode){
            if(ppnode->_left==parent){
                ppnode->_left=cur;
                cur->_parent=ppnode;
            }
            else{
                ppnode->_right=cur;
                cur->_parent=ppnode;
            }
        }
        else{
            cur->_parent=nullptr;
            _root=cur;
        }

        cur->_bf=parent->_bf=0;
    }

    //右左双旋
    void RotateRL(Node* parent){
        Node* cur=parent->_right;
        Node* curleft=cur->_left;
        int bf=curleft->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        if(bf==0){
            cur->_bf=0;
            curleft->_bf=0;
            parent->_bf=0;
        }

        else if(bf==1){
            cur->_bf=0;
            curleft->_bf=0;
            parent->_bf=-1;
        }

        else if(bf==-1){
            cur->_bf=1;
            curleft->_bf=0;
            parent->_bf=0;
        }

        else{
            assert(false);
        }

    }

    //左右双旋
    void RotateLR(Node* parent){
        Node* cur=parent->_left;
        Node* curright=cur->_right;
        int bf=curright->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        if(bf==0){
            cur->_bf=0;
            curright->_bf=0;
            parent->_bf=0;
        }
        
        else if(bf==-1){
            cur->_bf=0;
            curright->_bf=0;
            parent->_bf=1;
        }

        else if(bf==1){
            cur->_bf=-1;
            curright->_bf=0;
            parent->_bf=0;
        }

        else{
            assert(false);
        }

    }


private:
    Node* _root;
};